package ShortestPath;

import java.util.*;

public class CutOffTreesForGolfEvent {
    int m; // 对应 x 坐标
    int n; // 对应 y 坐标

    public int cutOffTree(List<List<Integer>> forest) {
        m = forest.size();
        n = forest.get(0).size();

        // 用数组保存所有 "树" 的坐标(1不是树, 是地面)
        List<int[]> coord = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (forest.get(i).get(j) > 1) {
                    // 1 位置是地面, 不需要砍树, 因此没必要包含进来
                    coord.add(new int[] { i, j });
                }
            }
        }
        // 将树的坐标由低到高排序(o1和o2分别是树的坐标[0]是行,[1]是列)
        Collections.sort(coord, (o1, o2) -> {
            return forest.get(o1[0]).get(o1[1]) - forest.get(o2[0]).get(o2[1]);
        });

        // 若干个迷宫问题
        int Ox = 0, Oy = 0; // 题目中提到每次都是从原点(0,0)开始走
        int ret = 0;
        for(int[] next : coord) {
            // 最低树的坐标
            int x = next[0], y = next[1];
            int step = bfs(forest, new int[] { Ox, Oy }, new int[] { x, y });
            if(step == -1) {
                return -1;
            }
            ret += step;
            // 找完后, 从该位置继续找下一棵树
            Ox = x;
            Oy = y;
        }

        return ret;
    }

    // 辅助向量数组
    int[] dx = { 1, -1, 0, 0 };
    int[] dy = { 0, 0, 1, -1 };

    boolean[][] visit; // 记录已经访问过的点

    // 层序遍历, 找出 start 到 end 的最短距离
    public int bfs(List<List<Integer>> forest, int[] start, int[] end) {
        if (start[0] == end[0] && start[1] == end[1]) {
            // 如果两个坐标位置相同, 不需要走, 返回0
            // 针对示例3: 树如果处于原点, 可以直接砍去, 不用算步数
            return 0;
        }
        visit = new boolean[m][n];

        // 用队列存储符合要求的点
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(start);
        visit[start[0]][start[1]] = true;
        int step = 0;

        while (!queue.isEmpty()) {
            // 走到这说明要往外扩一层
            step++;

            int size = queue.size();
            while (size-- != 0) {
                // 取出点
                int[] point = queue.poll();
                // 分解点坐标
                int Ox = point[0];
                int Oy = point[1];

                // 遍历下一层节点
                for (int i = 0; i < 4; i++) {
                    int x = Ox + dx[i];
                    int y = Oy + dy[i];

                    if (x >= 0 && x < m && y >= 0 && y < n && forest.get(x).get(y) != 0 && visit[x][y] == false) {
                        if (x == end[0] && y == end[1]) {
                            // 如果已经找到这个点, 返回step
                            return step;
                        }
                        queue.offer(new int[] { x, y });
                        visit[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }
}
